package vip.zhenzicheng.algorithm.leetcode.linked_list;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/lru-cache/">LRU缓存 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-22 14:16
 */
public class LRUCache_146 {

  /**
   * 主类
   */
  class LRUCache {

    // 缓存
    Map<Integer, LinkedList> cache = new HashMap<>();
    // 容量
    int capacity;
    // 头结点
    LinkedList head;
    // 尾节点
    LinkedList tail;

    public LRUCache(int capacity) {
      this.capacity = capacity;
      head = new LinkedList(-1, -1);
      tail = new LinkedList(-1, -1);
      // 头与尾节点相互指向
      head.next = tail;
      tail.pre = head;
    }

    public int get(int key) {
      LinkedList node = this.cache.get(key);
      if (node == null) {
        return -1;
      } else {
        // 移动到前面
        moveToFirst(node);
        return node.value;
      }
    }

    // 插入新节点
    private void addNewNode(LinkedList node) {
      LinkedList second = head.next;

      // 将新节点与头结点双向指定
      head.next = node;
      node.pre = head;
      // 将新节点与原来的第一个节点双向指定
      node.next = second;
      second.pre = node;

    }

    // 将旧节点移到最前面
    private void moveToFirst(LinkedList node) {
      // 将旧节点的前后节点相连
      LinkedList before = node.pre;
      LinkedList after = node.next;
      before.next = after;
      after.pre = before;

      // 当成新节点重新利用插入方法
      addNewNode(node);
    }

    public void put(int key, int value) {
      LinkedList node = this.cache.get(key);
      if (node == null) {
        if (this.cache.size() == this.capacity) {
          deleteLast();
        }
        LinkedList newNode = new LinkedList(key, value);
        addNewNode(newNode);
        this.cache.put(key, newNode);
      } else {
        node.value = value;
        this.cache.put(key, node);
        moveToFirst(node);
      }
    }

    private void deleteLast() {
      // 从链表中删除
      LinkedList prev = tail.pre;
      if (prev != head) {
        prev.pre.next = tail;
        tail.pre = prev.pre;

        // 从缓存中删除
        this.cache.remove(prev.key);
      }
    }

    /*双向链表*/
    class LinkedList {
      int key;
      int value;
      LinkedList pre;
      LinkedList next;

      LinkedList(int key, int value) {
        this.key = key;
        this.value = value;
      }
    }
  }
}
